package ch09_;

public class Ch9_1 {
	public static long countWays(int n) {
		if (n < 3) {
			return n;
		}
		long[] ways = new long[n + 1];
		ways[0] = 1;
		ways[1] = 1;
		ways[2] = 2;
		for (int i = 3; i < n + 1; i++) {
			ways[i] = ways[i - 3] + ways[i - 2] + ways[i - 1];
		}
		return ways[n];
	}
	
	public static void main(String[] args) {
		for (int i = 0; i < 1000; i++)
			System.out.println(i + " steps, " + countWays(i) + " ways to climb up.");
	}
}
